package basic;

import basic.study.algorithms.struct.Node;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Chapter7 {
    public static  void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = null;//n1
//        print(reverse(n1));
//        print(deleteLastKth(n1,2));
//        System.out.println(checkCircle(n1));
        System.out.println(findMiddleNode(n1).data);
    }
    public static void print(Node n){
        System.out.print("head");
        while(n != null) {
            System.out.print(" " + n.data);
            n = n.next;
        }
    }
    //单链表反转
    public static Node reverse(Node head) {
        Node curr = head;
        Node pre = null;
        while(curr != null) {
            Node next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    public static boolean checkCircle(Node head) {
        if(head == null || head.next == null) return false;
        Node fast = head.next;
        Node slow = head;
        int pos= 0 ;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            pos++;
            if(fast == slow) {
                System.out.println("pos: " + pos);
                return true;
            }
        }
        return false;
    }
    //合并两个链表
    public static Node mergeTwoNode(Node l1, Node l2) {
        Node solder = new Node(0);
        Node p = solder;
        while(l1 != null && l2 != null) {
            if(l1.data < l2.data) {
                p.next = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 != null) p = l1;
        if(l2 != null) p = l2;
        return solder.next;
    }

    // 删除倒数第K个结点
    public static Node deleteLastKth(Node list, int k) {
        Node slow = list;
        Node fast = list;
        Node pre = null;
        //fast和slow差k-1
        for(int i = 1; fast != null && i< k; i++) {
            fast = fast.next;
        }
        if(fast == null) {
            return list;
        }
        while(fast.next != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        if(pre == null) {
            list = list.next;
        } else {
            pre.next = pre.next.next;
        }
        return list;
    }
    // 求中间节点
    public static Node findMiddleNode(Node list) {
        if (list == null) return null;

        Node fast = list;
        Node slow = list;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return  slow;
    }
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {

            // Empty list
            if (head == null) {
                return null;
            }

            // Move the two pointers until they reach the proper starting point
            // in the list.
            ListNode cur = head, prev = null;
            while (m > 1) {
                prev = cur;
                cur = cur.next;
                m--;
                n--;
            }

            // The two pointers that will fix the final connections.
            ListNode con = prev, tail = cur;

            // Iteratively reverse the nodes until n becomes 0.
            ListNode third = null;
            while (n > 0) {
                third = cur.next;
                cur.next = prev;
                prev = cur;
                cur = third;
                n--;
            }

            // Adjust the final connections as explained in the algorithm
            if (con != null) {
                con.next = prev;
            } else {
                head = prev;
            }

            tail.next = cur;
            return head;
        }
    }
//
//    作者：LeetCode
//    链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

}
